Experimental Comparison of Disjoint and Overlapping Community Detection Algorithms in Simulated and Real World Networks

Abstract

In reality, networks do not divide themselves into perfectly disjointed communities. Proteins participate in multiple biological complexes; Web pages may belong to several topics. In order to address such a scenario, this paper examines existing community detection methods capable of detecting overlapping communities and compares their performance using experiments with LFR benchmark networks with various degrees of noise and real-world data sets (Karate Club, Dolphins, Les Misérables, Davis Women, Florentine Families). While Louvain algorithm turns out to be the fastest and the most efficient at low levels of noise and in case of distinct communities, its performance deteriorates sharply if ? > 0.4. SLPA is more stable in conditions of high noise and uses less memory. However, the algorithm requires proper threshold selection r ? 0.2–0.3 to achieve satisfactory results. BIGCLAM provides the best reconstruction of the underlying overlap structure but needs additional time resources. The stability test demonstrates similar output from the tested methods in multiple iterations. We present specific recommendations on when to use each algorithm.

Introduction

This paper provides a comprehensive study of community detection in networks, focusing on how nodes are grouped into communities and how different algorithms perform under varying conditions. Community detection is important in many domains, including social networks, biological systems, and information networks.

The study reviews the evolution of community detection from disjoint communities (where each node belongs to only one group) to overlapping communities (where nodes can belong to multiple groups) and dynamic communities that evolve over time. It evaluates three major algorithms—Louvain, SLPA, and BIGCLAM—using both synthetic LFR benchmark datasets and real-world networks.

Results show that Louvain is highly efficient and achieves excellent accuracy in networks with clear community structures, but its performance declines significantly in noisy networks and it cannot detect overlapping communities. SLPA supports overlapping memberships, performs better in noisy environments, and uses significantly less memory, although it is slower and sensitive to parameter settings. BIGCLAM provides expressive probabilistic modeling of overlapping communities but requires careful tuning.

The study further explores dynamic community detection, where communities can grow, shrink, merge, split, appear, or disappear over time. It also examines modern deep learning approaches, including Graph Neural Networks (GNNs), Graph Autoencoders, and Temporal GNNs, which improve community detection by combining network structure, node attributes, and temporal information.

Additionally, the paper discusses scalability challenges for large-scale networks, parallel processing techniques, robustness against adversarial attacks, and evaluation metrics such as NMI, ONMI, and the Omega Index. Based on extensive experiments, the authors recommend:

• Louvain for large networks with distinct communities and when speed is critical.
• SLPA for overlapping communities, noisy networks, or memory-constrained environments.
• BIGCLAM when the highest detection quality is required despite greater computational cost.

Conclusion

Real-life networks feature dynamic and overlapping community structures. While the disjoint model captures only some characteristics of such networks, the overlapping and the dynamic models capture others but at the price of higher complexity. In this paper, we provided the tradeoff analysis by creating the taxonomy of community structure detection approaches and conducting the comparative study on three selected algorithms. The findings are unambiguous: Louvain is the best choice among the compared algorithms in terms of performance and accuracy when the noise level is low (? ? 0.3). If the network has high noise levels and low memory, SLPA should be preferred. Finally, BIGCLAM provides the best recovery of the overlapping community structure if computational power is unlimited. Neither algorithm outperforms the others in all aspects. Community detection research is moving towards a unified framework for stream-based learning of models accounting for overlapping structure and attributes while being explainable. Achieving that goal requires addressing various challenges: from developing more appropriate benchmarks to finding solutions to ethics-related problems.

References

[1] Szabo, B. wrote about community detection in graphs in Physics Reports volume 486, pages 75 to 174, in the year 2010. [2] Reichardt, J. and Bornholdt, S. discussed the statistical mechanics of community detection in Physical Review E volume 78, article number 046110, published in 2008. [3] Lancichinetti, A. and Fortunato, S. conducted a comparative study on community detection algorithms which was published in Scientific Reports volume 1, article number 70, spanning pages 1 to 8, in 2011. [4] Watts, D.J. and Strogatz, S.H. examined the collective dynamics of small-world networks in Nature volume 393, pages 440 to 442, in the year 1998. [5] Yang, Z., Algesheimer, R., Tessone, C.J.: A comparison of community detection algorithms on artificial networks. Applied Network Science 8(1), 75 (2023) [6] Pröllochs, J., Xu, X., A., Islam: Community detection in complex networks: A systematic review. PLOS ONE 16(8), e0255717 (2021) [7] Sun, Y., Han, J., Yan, X., Yu, P.S., Wu, T.: PathSim: Meta path-based top-K similarity search in heterogeneous information networks. In: Proc. 21st Int. Conf. World Wide Web, pp. 539-548 (2012) [8] Chen, J., Saad, Y.: Dense subgraph extraction with the help of a graph-regularized optimization model. In: Proc. ACM SIGKDD 19 th. Conf. Knowledge Discovery and Data Mining, pp. 138-146 (2013) [9] Castrillo, E.: Disjoint and overlapping high quality community structures in large complex networks. arXiv:1805.12238 (2018) [10] Yang, J., Leskovec, J.: Community affiliation graph model of overlay network community detection. In: Proc. 2012 IEEE Int. Conf. Data Mining, pp. 1170–1175 (2012) [11] Chen, Z., Yang, J., Leskovec, J.: Supervised community detection with line graph neural networks. arXiv:1705.08415 (2017) [12] Baltsou, G., et al.: The causality of node participation in community structures. Information Sciences (2023) [13] Dao, V.L., Bothorel, C., Lenca, P.: Community structure: A comparative evaluation of community detection techniques. Network Science 8(1), 1–41 (2020) [14] Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmarks for testing community detection algorithms. Physical Review E 78(4), 046110 (2008) [15] Zachary, W.W.: Information flow model of conflict and fission in small groups. Journal of Anthropological Research 33(4), 452–473 (1977) [16] Lusseau, D., et al.: The bottlenose dolphin community of Doubtful Sound shows a high level of long term association. Behavioral Ecology and Sociobiology 54, 396–405 (2003) [17] Knuth, D.E.: The Stanford Graphbase: A Platform for Combinatorial Computing. Addison-Wesley, Reading, MA (1993) [18] Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99(12), 7821–7826 (2002) [19] Gleiser, P., Danon, L.: Community Structure in Jazz. Advances in Complex Systems 6(4), 565–573 (2003) [20] Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discoveryfrom Data 1(1), 1–40 (2007)

Copyright

Copyright © 2026 Ashima ., Ashi Srivastava, Simarjit Kaur. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.